package Test_1117;

import java.util.*;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
//用两个栈实现一个队列
class MyQueue {
    public Stack<Integer> stack1;
    public Stack<Integer> stack2;
    public MyQueue() {
           stack1=new Stack<>();
           stack2=new Stack<>();
    }
    //先将元素放到一个栈中
    public void push(int x) {
           if(empty()){
               stack1.push(x);
           }else if(!stack1.empty()) {
               stack1.push(x);
           }else {
               stack2.push(x);
           }
    }
    //
   /* public int pop() {

    }

    public int peek() {

    }*/

    public boolean empty() {
           return stack1.empty() && stack2.empty();
    }
}

//用队列实现栈
//用两个栈
//将元素都放到一个栈中
//将size-1个元素，放到另一个空栈中
//剩下的最后一个元素，弹出
class MyStack {
    public Queue<Integer> que1;
    public Queue<Integer> que2;
    public MyStack() {
        que1=new LinkedList<>();
        que2=new LinkedList<>();
    }
    //入栈：
    //判断栈是否为空：
    // 如果两个栈都为空。那么将元素先放入qu1中
    //如果有一个栈不为空，那么将元素先放入中不为空的栈中
    public void push(int x) {
        if(empty()){
            que1.offer(x);
        }else if(!que1.isEmpty()){
            que1.offer(x);
        }else{
            que2.offer(x);
        }
    }
    //出栈：
    //判断栈是否为空，为空返回
    //如果不为空，将不为空栈中的size-1元素个元素放到另一个栈中，将最后一个元素弹出
    public int pop() {
        int val=0;
        if(empty()){
            return -1;
        } else if(!que1.isEmpty()){
            int size=que1.size()-1;
            for (int i = 0; i < size; i++) {
                que2.offer(que1.poll());
            }
            val=que1.poll();
        }else{
            int size=que2.size()-1;
            for (int i = 0; i < size; i++) {
                que1.offer(que2.poll());
            }
            val=que2.poll();
        }
        return val;
    }
    //获取顶端元素：
    //与出栈差不多，不过最后一个不出栈
    public int top() {
        int val=0;
        if(empty()){
            return -1;
        } else if(!que1.isEmpty()){
            int size=que1.size();
            for (int i = 0; i < size; i++) {
                val=que1.poll();
                que2.offer(val);

            }

        }else{
            int size=que2.size();
            for (int i = 0; i < size; i++) {
                val=que2.poll();
                que1.offer(val);

            }
        }
        return val;
    }
    //栈是否为空：两个队列同时为空则为空
    public boolean empty() {
        return que1.isEmpty()&& que2.isEmpty();
    }
}
public class Soulution {
    //有效的括号
    //遍历字符串：
    //如果是左括号。将其放到栈中
    //如果不是左口号、、
    //1.栈为空且为右括号，返回false；
    //2.栈不为空，右括号与左括号相比较,
    // 如果不匹配返回false
    // 如果匹配，看栈是否为空
    public boolean isValid(String s) {
        Stack<Character> stack=new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c=s.charAt(i);
            if(isLeft(c)){
                stack.push(c);
            }else {
                if(stack.empty()){
                    return false;
                }
                char val=stack.peek();
                if( val=='(' && c==')'||val=='{' && c=='}' ||val=='[' && c==']'){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        return stack.empty();
    }
    public boolean isLeft(char s){
        if(s==('{')||s==('(')||s==('[')){
            return true;
        }
        return false;
    }
    //栈的压入、弹出序列
    //遍历数组中的元素
    //将栈中的顶元素与popV中的元素进行比较，如果相同，则将其弹出栈，并且j++
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack=new Stack<>();
        int j=0;
        for (int i = 0; i < pushV.length; i++) {
            int val=pushV[i];
            stack.push(val);
            while (j<popV.length &&!stack.empty()&&stack.peek()==popV[j]){
                stack.pop();
                j++;
            }
        }
        return stack.empty();
    }

}
